W13. Minimum spanning trees, disjoint-set union и алгоритм Краскала

1. Краткое содержание

1.1 Жадные алгоритмы

1.1.1 Задачи оптимизации

Многие важные алгоритмические задачи — это задачи оптимизации (optimization problems): задано большое (часто экспоненциальное) множество допустимых решений, каждому сопоставлена стоимость или ценность, и нужно найти решение с минимальной (или максимальной) стоимостью. Такие постановки узнаваются по словам вроде «кратчайший», «минимальный», «максимальный», «дешевле всего».

Установить, существует ли путь из \(u\) в \(v\), — задача распознавания (decision problem); найти кратчайший путь — задача оптимизации (optimization problem). Различие важно: перебор всех допустимых решений «в лоб» для оптимизации обычно неподъёмен по времени.

1.1.2 Жадная схема

Жадный алгоритм (greedy algorithm) строит решение по шагам: на каждом шаге выбирается локально «самый выгодный» вариант, фиксируется без отката. Схема привлекательна скоростью и простотой, но не универсальна — для многих задач корректного жадного алгоритма не существует. Для задач этой лекции (minimum spanning trees) жадные шаги доказуемо дают глобальный оптимум; ключевая идея — свойство разреза (cut property), которое это обосновывает.

1.2 Остовные деревья минимального веса

1.2.1 Остовные деревья и вес

Пусть \(G = (V, E)\) — связный неориентированный граф. Остовное дерево (spanning tree) \(G\) — это множество рёбер \(T \subseteq E\) такое, что \((V, T)\) связно и ациклично; иначе говоря, \(T\) — дерево, охватывающее все вершины. В дереве на \(|V|\) вершинах всегда ровно \(|V| - 1\) ребро.

Если рёбра имеют вещественные веса (weights), то вес остовного дерева — сумма весов его рёбер:

\[w(T) = \sum_{e \in T} w(e).\]

Остовное дерево минимального веса (minimum spanning tree, MST) — остовное дерево с минимальным суммарным весом. Если все веса равны, любое остовное дерево — MST.

Частый вариант: если \(G\) несвязен, остового дерева нет, но всегда есть остовный лес (spanning forest) — объединение остовных деревьев по одному на каждую компоненту связности. Минимальный по весу вариант — minimum spanning forest. Задачу можно свести к связному случаю, добавив между компонентами искусственные рёбра веса \(0\).

История MST восходит к 1926 году, когда Отакар Боржувака искал экономичную схему электроснабжения Моравии — соединить все пункты при минимальной суммарной длине кабеля.

1.2.2 Пример: поиск MST

Рассмотрим взвешенный неориентированный граф на шести вершинах \(A\)–\(F\):

MST состоит из рёбер \(A\)–\(D\) (4), \(C\)–\(E\) (5), \(A\)–\(B\) (6), \(C\)–\(F\) (6) и \(B\)–\(E\) (7); суммарный вес \(\mathbf{28}\).

1.2.3 Свойство разреза

Теоретическая основа алгоритмов MST — свойство разреза (cut property). Разрез (cut) \((S,\, V \setminus S)\) — разбиение множества вершин на две непустые части. Разрез согласован (respects) с множеством рёбер \(A\), если ни одно ребро из \(A\) не пересекает разрез (нет концов в \(S\) и \(V \setminus S\) одновременно). Лёгкое ребро (light edge) для разреза — ребро минимального веса среди всех пересекающих разрез.

Теорема (свойство разреза, Cormen et al. 2022, Thm. 21.1). Пусть \(A \subseteq E\) содержится в некотором MST графа \(G\). Пусть \((S,\, V \setminus S)\) — любой разрез, согласованный с \(A\), и пусть \((u, v)\) — лёгкое ребро, пересекающее этот разрез. Тогда \(A \cup \{(u, v)\}\) также содержится в некотором MST.

Наглядно: есть частичное решение MST; разрез проведён так, что выбранные рёбра разрез не пересекают; тогда самое дешёвое пересекающее ребро безопасно добавить. И алгоритм Прима (Prim’s algorithm), и алгоритм Краскала (Kruskal’s algorithm) можно рассматривать как многократное применение этого правила.

1.3 Алгоритм Прима

1.3.1 Обзор

Алгоритм Прима наращивает MST от одной корневой вершины \(r\). Поддерживается фронтир вершин ещё не в дереве; у каждой хранится ключ (key) — вес самого дешёвого ребра, соединяющего эту вершину с текущим деревом. На каждом шаге из фронтира извлекается вершина с минимальным ключом, она включается в дерево, ключи соседей обновляются при обнаружении более дешёвого подключения. Алгоритм завершается, когда все вершины в дереве.

Корректность шага следует из свойства разреза: когда извлекается вершина \(u\) (минимальный ключ среди вершин вне дерева), ребро \((u.\pi, u)\) веса \(u.\text{key}\) — лёгкое ребро для разреза между текущим деревом и остальным графом.

Отличие от наивного подхода: у Прима в очереди вершины (не рёбра), каждая вершина попадает в очередь не более одного раза, а уменьшение ключа делается эффективно. Наивный вариант со вставкой всех кандидатных рёбер в очередь даёт \(O(|E|)\) записей в очереди и худшую суммарную производительность.

1.3.2 Псевдокод

MST-PRIM(G, w, r)
1  for each vertex u ∈ G.V
2      u.key = ∞
3      u.π  = NIL
4  r.key = 0
5  Q = ∅
6  for each vertex u ∈ G.V
7      INSERT(Q, u)
8  while Q ≠ ∅
9      u = EXTRACT-MIN(Q)           // финализируем u; ребро (u.π, u) входит в MST
10     for each vertex v in G.Adj[u]  // релаксация соседей, ещё лежащих в Q
11         if v ∈ Q and w(u, v) < v.key
12             v.π  = u
13             v.key = w(u, v)
14             DECREASE-KEY(Q, v, w(u, v))

После завершения MST задаётся указателями предшественника: для каждой вершины \(u \ne r\) ребро \((u.\pi, u)\) принадлежит MST.

1.3.3 Анализ сложности

Сложность зависит от реализации очереди с приоритетом (priority queue).

Строки 1–3: инициализация ключей — \(\Theta(|V|)\).

Строки 6–7: вставка всех вершин в \(Q\) — \(\Theta(|V| \log |V|)\) для бинарной кучи, \(\Theta(|V|)\) для Fibonacci heap.

Строка 9: EXTRACT-MIN вызывается \(|V|\) раз: при бинарной куче каждый вызов \(O(\log |V|)\), итого \(\Theta(|V| \log |V|)\).

Строки 11–14: DECREASE-KEY не более одного раза на ребро — до \(|E|\) вызовов; с бинарной кучей каждый \(O(\log |V|)\), суммарно \(\Theta(|E| \log |V|)\). С Fibonacci heap DECREASE-KEY амортизированно \(O(1)\), суммарно \(\Theta(|E|)\) на этом шаге.

Очередь с приоритетом	Полное время
Binary min-heap	\(\Theta(|E| \log |V|)\)
Fibonacci heap	\(\Theta(|E| + |V| \log |V|)\)

Для простых графов \(\log |E| = \Theta(\log |V|)\) (так как \(|E| \le |V|^2\)), поэтому в логарифме можно писать \(|V|\) или \(|E|\).

Для плотных графов (\(|E| = \Theta(|V|^2)\)) Fibonacci heap даёт \(\Theta(|V|^2)\) — лучше, чем \(\Theta(|V|^2 \log |V|)\) у бинарной кучи. Для разреженных (\(|E| = \Theta(|V|)\)) обе реализации дают \(\Theta(|V| \log |V|)\).

1.4 Структуры данных для системы непересекающихся множеств

1.4.1 Мотивация и интерфейс

Во многих приложениях нужно поддерживать динамическую коллекцию попарно непересекающихся (disjoint) множеств над универсумом элементов и выполнять две операции:

• определить, какому множеству принадлежит элемент;
• объединить два множества.

Абстрактный тип disjoint-set (также union–find или DSU) поддерживает ровно это. Формально:

• MAKE-SET(x) — создать новое одноэлементное множество \(\{x\}\).
• FIND-SET(x) — вернуть указатель на представителя (representative) множества, содержащего \(x\). Все элементы одного множества должны давать одного и того же представителя.
• UNION(x, y) — объединить множества, содержащие \(x\) и \(y\).

Представитель — произвольный «идентификатор» множества. Важно, чтобы FIND-SET возвращал один и тот же указатель для всех элементов множества; иначе сравнение представителей не проверит принадлежность к одному множеству.

DSU используют в: компонентах связности неориентированных графов, алгоритме Краскала для MST, классах эквивалентности в символьных вычислениях, сегментации изображений, congruence closure в SMT-решателях.

1.4.2 Представление связными списками

Простейшая реализация: каждое множество — односвязный список; голова — представитель; в узле элемент, указатель на следующий узел и обратный указатель на голову.

• MAKE-SET(x): список из одного элемента — \(O(1)\).
• FIND-SET(x): по обратному указателю к голове — \(O(1)\).
• UNION(x, y): приписать список одного множества к другому и обновить обратные указатели у всех перенесённых узлов.

В наивном варианте UNION стоит \(\Theta(n)\) в худшем случае: при неудачном порядке обход обновления затрагивает все элементы.

Взвешенное объединение (union by size). Всегда приписывать короткий список к длинному, обновляя указатели только на короткой стороне.

Теорема. При связных списках и union by size указатель представителя у каждого элемента обновляется не более \(\lfloor \log_2 n \rfloor\) раз за всё время, где \(n\) — общее число элементов.

Идея доказательства. Обновление бывает только когда множество элемента — «меньшая сторона» в UNION. После обновления размер множества элемента хотя бы удваивается. Удвоений не больше \(\log_2 n\) на элемент. \(\square\)

Следствие: после \(n\) вызовов MAKE-SET и произвольного числа UNION суммарно \(O(n \log n)\) обновлений указателей, амортизированно \(O(\log n)\) на UNION.

1.4.3 Лес непересекающихся множеств

Эффективнее представлять каждое множество как корневое дерево; корень — представитель. У каждой нелистовой вершины указатель на родителя; у корня — на себя.

Наивные операции на дереве:

• MAKE-SET(x): \(\text{parent}[x] = x\) — \(O(1)\).
• FIND-SET(x): подъём по родителям до корня — \(O(\text{глубина})\).
• UNION(x, y): подвесить корень одного дерева под корень другого — \(O(1)\) после нахождения корней.

Без балансировки цепочка UNION может дать высоту \(\Theta(n)\) и FIND-SET за \(\Theta(n)\).

1.4.4 Union by rank

Union by rank хранит у каждого корня ранг (rank) — верхнюю оценку высоты поддерева. При слиянии:

• если ранги различны, корень с меньшим рангом подвешивается под корень с большим;
• если ранги равны, выбирается новый корень и его ранг увеличивается на 1.

Лемма. При union by rank (без path compression) дерево с корнем ранга \(k\) содержит не менее \(2^k\) вершин.

Доказательство. Индукция по \(k\). Для \(k=0\) — одна вершина. Слияние двух деревьев ранга \(k\) даёт не менее \(2^k + 2^k = 2^{k+1}\) вершин и ранг \(k+1\). При слиянии рангов \(j < k\) и \(k\) итоговый ранг \(k\) и размер \(\ge 2^j + 2^k \ge 2^k\). \(\square\)

Следствие. Только с union by rank высота любого дерева \(\le \lfloor \log_2 n \rfloor\), значит FIND-SET и UNION — \(O(\log n)\) в худшем случае.

1.4.5 Path compression

Path compression ускоряет FIND-SET: после нахождения корня для \(x\) все вершины на пути перенаправляют родителя сразу на корень; последующие поиски для них быстрее.

Слева: цепочка до path compression. Справа: после FIND-SET(g) вершины \(g\), \(d\) и \(b\) указывают прямо на корень \(a\).

Path compression не пересчитывает ранги — они могут завышать высоту, но остаются корректными верхними оценками, union by rank продолжает работать.

1.4.6 Совместная сложность: rank + path compression

При объединении union by rank и path compression амортизированная стоимость операции — \(O(\alpha(n))\), где \(\alpha\) — обратная функция Аккермана (inverse Ackermann function) (раздел 1.6). На практике \(\alpha(n) \le 4\).

Псевдокод:

MAKE-SET(x)
1  x.p    = x
2  x.rank = 0

FIND-SET(x)                         // path compression
1  if x ≠ x.p
2      x.p = FIND-SET(x.p)
3  return x.p

UNION(x, y)
1  LINK(FIND-SET(x), FIND-SET(y))

LINK(x, y)                          // union by rank
1  if x.rank > y.rank
2      y.p = x
3  else x.p = y
4      if x.rank == y.rank
5          y.rank = y.rank + 1

Рекурсия в FIND-SET, строка 2, и есть path compression: на обратном проходе от корня родитель каждой вершины на пути становится найденным корнем.

1.4.7 Сравнение представлений

Представление	MAKE-SET	FIND-SET	UNION
Списки (наивный union)	\(\Theta(1)\)	\(\Theta(1)\)	\(\Theta(n)\) худший
Списки (union by size)	\(\Theta(1)\)	\(\Theta(1)\)	\(O(\log n)\) аморт.
Лес (наивный)	\(\Theta(1)\)	\(\Theta(n)\) худший	\(\Theta(n)\) худший
Лес (union by rank)	\(\Theta(1)\)	\(O(\log n)\)	\(O(\log n)\)
Лес (rank + path compression)	\(\Theta(1)\)	\(O(\alpha(n))\) аморт.	\(O(\alpha(n))\) аморт.

Лес с обоими приёмами — стандарт на практике (Cormen et al. 2022, §19.3–19.4).

1.5 Алгоритм Краскала

1.5.1 Обзор

Алгоритм Краскала обрабатывает рёбра в порядке неубывания веса и жадно добавляет ребро к лесу, если оно соединяет две ранее несвязанные компоненты. DSU проверяет связность и объединяет компоненты.

Алгоритм:

1. Инициализировать \(|V|\) одноэлементных множеств: MAKE-SET(v) для всех \(v \in V\).
2. Отсортировать все рёбра по неубыванию веса: \(O(|E| \log |E|)\).
3. Для каждого ребра \((u, v)\) в этом порядке:
   • если FIND-SET(u) \(\neq\) FIND-SET(v) — ребро между разными компонентами: добавить в MST и вызвать UNION(u, v).
4. Остановиться после добавления \(|V| - 1\) ребра (для связного графа это всегда произойдёт).

Корректность. Каждое добавленное ребро безопасно по свойству разреза: это лёгкое ребро для разреза между компонентой \(u\) и компонентой \(v\) в момент обработки (более дешёвого пересечения между этими компонентами нет: все лёгче уже обработаны и либо добавлены, либо создали бы цикл внутри одной компоненты).

1.5.2 Время работы

• Сортировка: \(O(|E| \log |E|) = O(|E| \log |V|)\), так как \(|E| \le |V|^2\) даёт \(\log |E| \le 2 \log |V|\).
• Операции DSU: до \(O(|E|)\) вызовов FIND-SET и UNION, каждый \(O(\alpha(|V|))\) амортизированно, итого \(O(|E|\, \alpha(|V|))\).
• Итого: обычно доминирует сортировка — \(O(|E| \log |V|)\).
• Частный случай: рёбра уже отсортированы (например, целые веса и radix sort) — доминирует DSU: \(O(|E|\, \alpha(|V|))\).

1.5.3 Пример выполнения

Тот же граф на 6 вершинах (\(A\)–\(F\)), рёбра по неубыванию веса:

Шаг	Ребро	Вес	Действие
1	\(A\)–\(D\)	4	Разные компоненты — добавить
2	\(C\)–\(E\)	5	Разные компоненты — добавить
3	\(A\)–\(B\)	6	Разные компоненты — добавить
4	\(C\)–\(F\)	6	Разные компоненты — добавить
5	\(B\)–\(D\)	7	Уже в одной компоненте с \(A\)–\(D\) — пропустить
6	\(B\)–\(E\)	7	Разные компоненты — добавить (соединяет \(\{A,B,D\}\) и \(\{C,E,F\}\))

После шага 6 все 6 вершин связаны 5 рёбрами: вес MST \(= 4+5+6+6+7 = \mathbf{28}\).

1.6 Функция Аккермана и обратная к ней

1.6.1 Определение

Функция Аккермана (Ackermann function) \(A_k(j)\) задаётся двойной рекурсией (Cormen et al. 2022, §19.4):

\[A_k(j) = \begin{cases} j + 1 & \text{if } k = 0, \\ A_{k-1}^{(j+1)}(j) & \text{if } k > 0, \end{cases}\]

где \(A_k^{(i)}(j)\) — \(i\)-кратное применение \(A_k\), начиная с \(j\):

\[A_k^{(i)}(j) = \underbrace{A_k(A_k(\cdots(A_k(j))\cdots))}_{\text{ровно } i \text{ применений}}.\]

Наглядно: \(A_0\) — следующий аргумент; \(A_1\) итерирует \(A_0\), даёт \(A_1(j) = 2j + 1\); \(A_2\) итерирует \(A_1\) — экспоненциальный рост; \(A_3\) — «башня» экспонент; каждый уровень растёт астрономически быстрее предыдущего.

Ключевые значения:

\[A_0(1) = 2, \quad A_1(1) = 3, \quad A_2(1) = 7, \quad A_3(1) = 2047, \quad A_4(1) \gg 2^{2^{2^{\cdots^{2047}}}}.\]

1.6.2 Обратная функция Аккермана

Обратная функция Аккермана \(\alpha(n)\) — минимальное \(k\) такое, что \(A_k(1) \ge n\):

\[\alpha(n) = \min\{k \mid A_k(1) \ge n\}.\]

Из таблицы значений:

\[\alpha(n) = \begin{cases} 0 & 0 \le n \le 2, \\ 1 & n = 3, \\ 2 & 4 \le n \le 7, \\ 3 & 8 \le n \le 2047, \\ 4 & 2048 \le n \le A_4(1). \end{cases}\]

Число \(A_4(1)\) астрономически велико (башня из 2047 двоек), поэтому \(\alpha(n) \le 4\) для любого \(n\), встречающегося на практике (например, при \(n \le 2^{65536}\)). Амортизированную сложность \(O(\alpha(n))\) для DSU на практике считают по сути \(O(1)\).

---

2. Определения

• Задача оптимизации (optimization problem): выбрать среди всех допустимых решений решение с минимальной (или максимальной) стоимостью.
• Жадный алгоритм (greedy algorithm): строит решение по шагам, на каждом шаге делает локально самый дешёвый выбор без отката.
• Остовное дерево (spanning tree): для связного неориентированного \(G = (V, E)\) — подмножество \(T \subseteq E\) такое, что \((V, T)\) связно и ациклично; ровно \(|V| - 1\) ребро.
• MST (minimum spanning tree): остовное дерево минимального суммарного веса рёбер.
• Остовный лес (spanning forest): для несвязного графа — максимальный ацикличный подграф: по остовному дереву на каждую компоненту связности.
• Вес остовного дерева: \(w(T) = \sum_{e \in T} w(e)\).
• Разрез \((S, V \setminus S)\): разбиение \(V\) на два непустых непересекающихся подмножества.
• Разрез согласован с \(A\): ни одно ребро из \(A\) не имеет концы по разные стороны разреза.
• Лёгкое ребро (light edge): ребро минимального веса среди пересекающих данный разрез.
• Свойство разреза (cut property): если \(A \subseteq E\) лежит в некотором MST и разрез согласован с \(A\), то любое лёгкое ребро для этого разреза можно безопасно добавить к \(A\), сохранив инвариант «часть некоторого MST».
• Алгоритм Прима (Prim’s algorithm): жадный MST: наращивает одно дерево, многократно добавляя самое дешёвое ребро из дерева к вершине вне дерева; использует очередь с приоритетом по вершинам с ключом — минимальной стоимости подключения к текущему MST.
• Ключ (key) у Прима: \(v.\text{key}\) — минимальный вес ребра, соединяющего \(v\) с текущим MST.
• Предшественник (predecessor) \(v.\pi\): вершина в MST, через которую достигается минимальный вес подключения \(v\).
• DSU (disjoint-set / union–find): АТД, поддерживающий разбиение универсума на непересекающиеся множества с операциями MAKE-SET, FIND-SET, UNION.
• Представитель (representative): выделенный элемент множества; FIND-SET(x) возвращает представителя множества, содержащего \(x\).
• Ранг (rank): в лесу DSU — верхняя оценка высоты поддерева с корнем в данной вершине; используется в union by rank.
• Union by rank: подвешивать корень с меньшим рангом под корень с большим; при равенстве рангов увеличить ранг нового корня на 1.
• Path compression: при FIND-SET(x) перенаправить каждую вершину на пути к корню сразу на корень.
• Алгоритм Краскала (Kruskal’s algorithm): сортирует рёбра по весу и добавляет ребро, если оно соединяет две разные компоненты (учёт компонент через DSU).
• Функция Аккермана \(A_k(j)\): рекурсивно определённая функция, растущая быстрее любой примитивно рекурсивной; \(A_0(j)=j+1\), \(A_k(j)=A_{k-1}^{(j+1)}(j)\) при \(k>0\).
• Обратная к Аккерману \(\alpha(n)\): \(\alpha(n) = \min\{k \mid A_k(1) \ge n\}\); растёт настолько медленно, что на практике \(\alpha(n) \le 4\).

---

3. Формулы

• Вес MST: \(w(T) = \displaystyle\sum_{e \in T} w(e)\)
• Прима — binary heap: \(\Theta(|E| \log |V|)\)
• Прима — Fibonacci heap: \(\Theta(|E| + |V| \log |V|)\)
• Взвешенный union (списки): указатель представителя у элемента обновляется не более \(\lfloor \log_2 n \rfloor\) раз за все операции.
• Union by rank — нижняя оценка размера: у корня ранга \(k\) в поддереве не менее \(2^k\) вершин.
• Union by rank — граница высоты: без path compression высота \(\le \lfloor \log_2 n \rfloor\).
• Краскал — общий случай: \(O(|E| \log |V|)\) (доминирует сортировка)
• Краскал — рёбра уже отсортированы: \(O(|E|\,\alpha(|V|))\) (доминирует DSU)
• Аккерман, база: \(A_0(j) = j + 1\)
• Аккерман, рекурсия: \(A_k(j) = A_{k-1}^{(j+1)}(j)\) при \(k > 0\)
• Уровень 1: \(A_1(j) = 2j + 1\) для всех \(j \ge 1\)
• Уровень 2: \(A_2(j) = 2^{j+1}(j+1) - 1\) для всех \(j \ge 1\)
• Обратная функция Аккермана: \(\alpha(n) = \min\{k \mid A_k(1) \ge n\}\)

---

4. Примеры

4.1. Трассировка алгоритма Прима на взвешенном графе (Лекция 11, Пример 1)

Примените наивную эвристику «минимальное ребро» и алгоритм Прима к графу из §1.2.2, показав, как меняется очередь с приоритетом.

Нажмите, чтобы увидеть решение

Наивная эвристика (старт из \(A\), в очереди рёбра с фронтира):

Шаг	Добавленная вершина	Использованное ребро	Очередь после извлечения (кандидатные рёбра)
0	—	—	\(\{A\text{–}B(6),\, A\text{–}D(4)\}\)
1	\(D\)	\(A\)–\(D\) (4)	\(\{A\text{–}B(6),\, D\text{–}B(7),\, D\text{–}E(12),\, D\text{–}C(8)\}\)
2	\(B\)	\(A\)–\(B\) (6)	\(\{D\text{–}B(7),\, B\text{–}E(7),\, D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}\)
3	(пропуск)	\(D\)–\(B\) (7): \(B\) уже в дереве	далее минимум \(B\)–\(E\) (7)
3\('\)	\(E\)	\(B\)–\(E\) (7)	\(\{E\text{–}C(5),\, D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}\)
4	\(C\)	\(E\)–\(C\) (5)	\(\{C\text{–}F(6),\, D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}\)
5	\(F\)	\(C\)–\(F\) (6)	оставшиеся рёбра только внутри дерева / лишние

Полная трассировка даёт рёбра MST \(A\)–\(D\), \(A\)–\(B\), \(B\)–\(E\), \(C\)–\(E\), \(C\)–\(F\) при суммарном весе 28.

Замечание о сложности. Наивный подход вставляет до \(\deg(u)\) новых рёбер после каждого извлечения; очередь может разрастись до \(O(|E|)\) записей, суммарная стоимость порядка \[\sum_{u} \bigl[O(\log|E|) + \deg(u) \cdot O(\log|E|)\bigr] = O\bigl((|V| + |E|)\log|V|\bigr) = O(|E|\log|V|).\]

Алгоритм Прима (старт из \(A\), в очереди вершины с ключом — минимальное известное подключение к дереву):

Шаг	EXTRACT-MIN	Ребро MST	Релаксация соседей
0	\(A\) (\(\text{key}=0\))	—	\(B.\text{key} \leftarrow 6\), \(\pi=B\); \(D.\text{key} \leftarrow 4\), \(\pi=D\)
1	\(D\) (\(\text{key}=4\))	\(A\)–\(D\) (4)	\(B\): без изменений (7>6); \(C.\text{key} \leftarrow 8\), \(\pi=D\); \(E.\text{key} \leftarrow 12\), \(\pi=D\)
2	\(B\) (\(\text{key}=6\))	\(A\)–\(B\) (6)	\(C\): 10 не лучше 8; \(E.\text{key} \leftarrow 7\), \(\pi=B\)
3	\(E\) (\(\text{key}=7\))	\(B\)–\(E\) (7)	\(C.\text{key} \leftarrow 5\), \(\pi=E\)
4	\(C\) (\(\text{key}=5\))	\(C\)–\(E\) (5)	\(F.\text{key} \leftarrow 6\), \(\pi=C\)
5	\(F\) (\(\text{key}=6\))	\(C\)–\(F\) (6)	—

Рёбра MST: \(A\)–\(D\) (4), \(A\)–\(B\) (6), \(B\)–\(E\) (7), \(C\)–\(E\) (5), \(C\)–\(F\) (6). Сумма \(=\mathbf{28}\).

Каждая вершина входит в очередь один раз, DECREASE-KEY — не более одного раза на ребро, число операций с очередью \(O(|V| + |E|)\), с бинарной кучей — улучшенная оценка \(O(|E| \log |V|)\).

4.2. Наивная эвристика MST со старта из вершины A (Лекция 11, Пример 2)

Примените наивную эвристику «минимальное ребро» к графу из §1.2.2 (вершины \(A\)–\(F\)), начиная с \(A\). Перечислите рёбра на каждом шаге и состояние очереди (рёбра). Укажите структуру данных для эффективной реализации.

Нажмите, чтобы увидеть решение

Инициализация. Старт из \(A\). В очереди все инцидентные \(A\) рёбра:

\[Q = \{A\text{–}D(4),\, A\text{–}B(6)\}.\]

Шаг 1. Извлечь минимум: \(A\)–\(D\) (4). Добавить \(D\). Вставить рёбра из \(D\) к вершинам вне дерева: \(D\)–\(B\) (7), \(D\)–\(E\) (12), \(D\)–\(C\) (8). Ребро \(D\)–\(A\) пропустить.

\[Q = \{A\text{–}B(6),\, D\text{–}C(8),\, D\text{–}B(7),\, D\text{–}E(12)\}.\]

Рёбра дерева: \(\{A\text{–}D\}\).

Шаг 2. Минимум: \(A\)–\(B\) (6). Добавить \(B\). Вставить \(B\)–\(C\) (10), \(B\)–\(E\) (7). \(B\)–\(D\) пропустить (\(D\) в дереве).

\[Q = \{D\text{–}B(7),\, B\text{–}E(7),\, D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}.\]

Рёбра: \(\{A\text{–}D,\, A\text{–}B\}\).

Шаг 3. Минимум \(D\)–\(B\) (7), но \(B\) уже в дереве — отбросить.

Следующий минимум: \(B\)–\(E\) (7). Добавить \(E\). Из \(E\): \(E\)–\(C\) (5); \(E\)–\(D\) пропустить.

\[Q = \{E\text{–}C(5),\, D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}.\]

Рёбра: \(\{A\text{–}D,\, A\text{–}B,\, B\text{–}E\}\).

Шаг 4. Минимум: \(E\)–\(C\) (5). Добавить \(C\). Из \(C\): \(C\)–\(F\) (6); \(C\)–\(D\), \(C\)–\(B\) пропустить.

\[Q = \{C\text{–}F(6),\, D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}.\]

Рёбра: \(\{A\text{–}D,\, A\text{–}B,\, B\text{–}E,\, C\text{–}E\}\).

Шаг 5. Минимум: \(C\)–\(F\) (6). Добавить \(F\). Новых рёбер к вершинам вне дерева нет.

\[Q = \{D\text{–}C(8),\, B\text{–}C(10),\, D\text{–}E(12)\}.\]

Все 6 вершин в дереве — готово.

Вес MST: \(4 + 6 + 7 + 5 + 6 = \mathbf{28}\).

Структура данных: min-priority queue (например, binary min-heap) для извлечения минимального ребра; EXTRACT-MIN и INSERT по \(O(\log |E|) = O(\log |V|)\), суммарно \(O(|E| \log |V|)\).

4.3. Алгоритм Прима со старта из вершины L (Лекция 11, Пример 3)

Примените алгоритм Прима к 18-вершинному графу из упражнения 11.2 (вершины \(A\)–\(R\)), начиная с \(L\). Разрывы при равных ключах — по лексикографическому порядку имён соседей. Укажите порядок извлечения вершин из очереди и ребро MST для каждой добавленной вершины.

Нажмите, чтобы увидеть решение

Общая процедура.

1. Инициализация: \(L.\text{key} = 0\), остальные ключи \(\infty\), все вершины в мин-куче \(Q\).
2. Извлечь \(L\) (ключ 0). Для каждого соседа \(v\) вершины \(L\): если \(w(L,v) < v.\text{key}\), установить \(v.\text{key} \leftarrow w(L,v)\), \(v.\pi \leftarrow L\), вызвать DECREASE-KEY.
3. Извлечь вершину \(u\) с минимальным ключом (при равенстве — с меньшей меткой). Зафиксировать ребро \((u.\pi, u)\) в MST. Для каждого соседа \(v\) из \(u\), ещё в \(Q\): при \(w(u,v) < v.\text{key}\) обновить ключ и \(\pi\).
4. Повторять до опустошения \(Q\).

Инвариант: перед извлечением \(u\) значение \(u.\text{key}\) равно минимальному весу ребра от \(u\) к уже финализированному дереву.

Что записывать: на каждом шаге — извлечённая вершина, ребро MST \((u.\pi,u)\) и какие ключи соседей обновились.

Правило разрыва: при равных ключах извлекать вершину с лексикографически меньшей меткой; при равных весах рёбер к соседям порядок обхода не меняет итоговых ключей, если все обновления выполнить.

Ответ: конкретная последовательность извлечений и рёбер MST зависит от весов рёбер в графе на 18 вершинах; получите полный ответ, пошагово применяя процедуру с указанным разрывом.

4.4. Доказательство границы высоты при union by rank (Лекция 11, Пример 4)

Докажите: если используется только union by rank (без path compression), высота любого дерева в лесу не превосходит \(\lfloor \log_2 n \rfloor\), где \(n\) — суммарное число узлов во всех деревьях.

Нажмите, чтобы увидеть решение

Утверждение. При union by rank дерево с корнем ранга \(k\) содержит не менее \(2^k\) вершин.

Индукция по \(k\).

База (\(k = 0\)). После MAKE-SET у \(x\) ранг 0, дерево из одной вершины: \(1 = 2^0\). ✓

Шаг индукции. Пусть утверждение верно для рангов \(< k\). Пусть корень \(r\) имеет ранг \(k\). Ранг \(k\) возникает только при LINK двух деревьев одинакового ранга \(k-1\) (ранг увеличивается только в этом случае). К моменту слияния в каждом дереве не менее \(2^{k-1}\) вершин (по индукции). После слияния не менее \(2^{k-1} + 2^{k-1} = 2^k\) вершин; дальнейшие UNION только добавляют вершины. \(\square\)

Следствие (граница высоты). Всего не более \(n\) вершин и не менее \(2^k\) при ранге \(k\) корня: \(2^k \le n\), откуда \(k \le \lfloor \log_2 n \rfloor\).

Без path compression ранг корня совпадает с высотой при наращивании через равные ранги, поэтому высота \(\le \lfloor \log_2 n \rfloor\). Следовательно, FIND-SET — \(O(\log n)\), UNION — два FIND-SET плюс \(O(1)\) для LINK — тоже \(O(\log n)\). \(\square\)

4.5. Компоненты связности через DSU (Лекция 11, Пример 5)

Пусть \(G = (V, E)\) — неориентированный граф с \(n\) вершинами и \(m\) рёбрами. Опишите алгоритм на DSU, считающий число компонент связности. Оцените время. Как вывести размер каждой компоненты?

Нажмите, чтобы увидеть решение

Алгоритм.

CONNECTED-COMPONENTS(G)
1  for each vertex v in G.V
2      MAKE-SET(v)
3  for each edge (u, v) in G.E
4      if FIND-SET(u) ≠ FIND-SET(v)
5          UNION(u, v)
6  // подсчёт различных представителей
7  components = 0
8  for each vertex v in G.V
9      if FIND-SET(v) == v          // v — корень
10         components = components + 1
11 return components

Корректность. После обработки всех рёбер вершины \(u\) и \(v\) в одном множестве DSU тогда и только тогда, когда в \(G\) есть путь между ними. Число компонент равно числу различных представителей (= числу деревьев в лесу DSU).

Время.

• Строки 1–2: \(n\) вызовов MAKE-SET — \(O(n)\).
• Строки 3–5: \(m\) итераций, в каждой до двух FIND-SET и возможно UNION; с union by rank и path compression — \(O(\alpha(n))\) амортизированно на операцию, суммарно \(O(m\,\alpha(n))\).
• Строки 7–10: \(n\) вызовов FIND-SET — \(O(n\,\alpha(n))\).

Итого: \(O((n + m)\,\alpha(n))\), на практике близко к \(O(n + m)\).

Размеры компонент. Дополнительный массив size[v], изначально 1. В UNION(x, y) после нахождения корней \(r_x\), \(r_y\):

size[new_root] = size[r_x] + size[r_y]

где new_root — корень объединённого дерева. В конце для каждого корня \(v\) (FIND-SET(v)==v) значение size[v] — размер компоненты. Дополнительно \(O(1)\) на UNION, асимптотика не меняется.

4.6. Алгоритм Краскала на взвешенном графе (Лекция 11, Пример 6)

Примените алгоритм Краскала к 18-вершинному графу из упражнения 11.2. Укажите порядок обработки рёбер, какие рёбра вошли в MST, какие отклонены (цикл в одной компоненте), и состояние DSU после операций.

Нажмите, чтобы увидеть решение

Процедура.

1. Инициализация: MAKE-SET(v) для каждой из 18 вершин.
2. Сортировка рёбер по неубыванию веса. При равных весах порядок не меняет вес MST (возможны несколько MST).
3. Просмотр. Для \((u,v)\): \(r_u=\text{FIND-SET}(u)\), \(r_v=\text{FIND-SET}(v)\). Если \(r_u \ne r_v\) — добавить ребро в MST и UNION(u,v)$. Иначе отклонить.
4. Останов: после добавления 17 рёбер (для связного графа на 18 вершинах). Если граф связен, это произойдёт до исчерпания всех рёбер.

Отслеживать: после каждого принятого ребра — какие две компоненты слились.

Проверка: 17 рёбер образуют дерево (связность, ацикличность), суммарный вес минимален: любое более лёгкое пересекающее рёбра компоненты ребро обработано раньше.

Выполните процедуру по отсортированному списку рёбер для данного графа.

4.7. Значения функции Аккермана (Лекция 11, Пример 7)

Вычислите \(A_k(1)\) для \(k = 0, 1, 2, 3, 4\) по определению \(A_0(j) = j + 1\) и \(A_k(j) = A_{k-1}^{(j+1)}(j)\) при \(k > 0\).

Нажмите, чтобы увидеть решение

Напоминание: \(A_k^{(i)}(j)\) — \(i\) применений \(A_k\), начиная с \(j\). При \(k>0\) нужно применить \(A_{k-1}\) ровно \(j+1\) раз, начиная с \(j\).

\(k = 0\): \[A_0(1) = 1 + 1 = \mathbf{2}.\]

\(k = 1\): \[A_1(1) = A_0^{(2)}(1) = A_0(A_0(1)) = A_0(2) = 3.\]

Проверка по формуле \(A_1(j) = 2j + 1\): \(A_1(1) = 3\). ✓

\(k = 2\): \[A_2(1) = A_1^{(2)}(1) = A_1(A_1(1)) = A_1(3) = 7.\]

Итог: \(A_2(1) = \mathbf{7}\).

\(k = 3\): \[A_3(1) = A_2^{(2)}(1) = A_2(A_2(1)) = A_2(7).\]

\(A_2(7) = A_1^{(8)}(7)\); восемь раз применить \(A_1(j)=2j+1\) к 7: \[7 \to 15 \to 31 \to 63 \to 127 \to 255 \to 511 \to 1023 \to 2047.\]

\(A_3(1) = \mathbf{2047}\).

\(k = 4\): \[A_4(1) = A_3^{(2)}(1) = A_3(A_3(1)) = A_3(2047).\]

\(A_3(2047) = A_2^{(2048)}(2047)\). Так как \(A_2(j)\) очень быстро растёт с \(j\), после первых применений получаются колоссальные величины; после 2048 применений:

\[A_4(1) > \underbrace{2^{2^{2^{\cdots^{2047}}}}}_{\text{башня из 2047 двоек}}.\]

Число невыразимо в обычной записи; для порядка величины \(A_4(1) > 2^{65536}\), что больше грубых оценок числа атомов в наблюдаемой Вселенной.

Сводная таблица:

\(k\)	\(A_k(1)\)
0	2
1	3
2	7
3	2047
4	несоизмеримо велико

Значения \(\alpha(n)\):

Диапазон \(n\)	\(\alpha(n)\)
\(0 \le n \le 2\)	0
\(n = 3\)	1
\(4 \le n \le 7\)	2
\(8 \le n \le 2047\)	3
\(2048 \le n \le A_4(1)\)	4

Для любого реалистичного \(n\) в вычислениях \(\alpha(n) \le 4\).